/**
 * 173. 链表插入排序
 * 用插入排序对链表排序
 * https://www.lintcode.com/problem/insertion-sort-list/description
 * 
 * 样例
 * Given 1->3->2->0->null, return 0->1->2->3->null
 * 
 * 2018.12.28 @jeyming
 */
package insertion_sort_list_0173;

public class Insertion_sort_list_0173 {
	// Definition for ListNode
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}
	
	public ListNode insertionSortList(ListNode head) {
        // write your code here
		for (ListNode p = head; p != null; p = p.next) {
			for (ListNode q = p.next; q != null; q = q.next) {
				if (p.val > q.val) {
					int tmp = p.val;
					p.val = q.val;
					q.val = tmp;
				}
			}
		}
		return head;
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println("Helloworld!");
	}

}
